﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution797
{
    IList<IList<int>> paths = new List<IList<int>>();

    IList<int> path= new List<int>();
    public IList<IList<int>> AllPathsSourceTarget(int[][] graph)
    {

        path.Add(0);
        DFS(0, graph);
        return paths;

    }

    private void DFS(int cur, int[][] graph)
    {
        if (cur == graph.Length-1)//收集到最后一个数字了
        {

            paths.Add(new List<int>(path));
            return;
        }
        


        for (int i = 0; i < graph[cur].Length; i++) {//遍历当前数字可以到达的所有数字

            path.Add(graph[cur][i]);
            DFS(graph[cur][i], graph);

            //回溯

            //path.Remove(path.Count-1);
            path.RemoveAt(path.Count-1);
            //path.Remove(graph[cur][i]);
        }
    }
}


class Program797
{
    static void Main797(string[] args)
    {
        int[][] graph = [[1, 2], [3], [3], []];
        Solution797 solution = new Solution797();
        IList<IList<int>> paths= solution.AllPathsSourceTarget(graph);
        for(int i = 0;i < paths.Count;i++)
        {
            for(int j = 0; j < paths[i].Count; j++)
            {
                Console.Write(paths[i][j]);
            }
            Console.WriteLine();


        }
    }
}
